day 15 - Self Replicating Toy

Can you design your own self-replicating toy? Service: nc 3.93.128.89 1214 Download: chal.c

Recon

We're given a program in C that implements some virtual machine with a custom instruction set. The program accepts a program written for the VM from stdin and checks that the program's output is the program itself. If so, it prints the flag from flag.txt.

The idea is straightforward, we need to implement a program for that VM that is a quine.

Code

#!/usr/bin/env python
from functools import partial
from pwn import *

FTABLE_IDX = 0

def push(s):
    o = ord(s)
    if o < 0x80:
        return s
    return '{}\x80'.format(chr(o ^ 0x80))

def pushlist(l):
    pushseq = list(map(push, l))[::-1]
    return ''.join(pushseq)

def fun(inst, idx):
    return push('\xa1') + pushlist(inst) + push(chr(idx)) + '\xa0'

def call(idx):
    absidx = idx + 0xc0
    if absidx >= 0xe0:
        raise ValueError('Invalid function call index')

    return chr(absidx)


def ccall(idx):
    absidx = idx + 0xe0
    if absidx >= 0xe0 + 0x20:
        raise ValueError('Invalid function call index')
    return chr(absidx)

def binops(x):
    return x

def binop(x, a1, a2):
    return push(chr(a1)) + push(chr(a2)) + x

def dups():
    return '\x91'

def dup(a):
    return push(chr(a)) + dups()

def out(*args):
    return '\xb0'

def printf(s):
    return pushlist(s) + ''.join([out() for _ in s])

band = partial(binop, '\x82')
bands = partial(binops, '\x82')
bor = partial(binop, '\x83')
bors = partial(binops, '\x82')
bxor = partial(binop, '\x84')
bxors = partial(binops, '\x84')
swap = partial(binop, '\x90')
swaps = partial(binops, '\x90')
tests = partial(binops, '\x81')

def test():
    out_shit = printf('Hello, world!')
    mfun = fun(out_shit, 0)
    return mfun + call(0)

def program():
    # data function representation
    # \x00 (signifies end of data) .. c0 \x01 c1 \x01 c2 \x01 ...
    def reps(s):
        pushes = [push(x) for x in s]
        string = '\x00'
        for x in pushes:
            string += x
            string += push('\x01')
        return string

    ## OUTPUT 1 char
    output = fun(out(), 1)


    # called if and only if (iff) there is a char on the stack that is larger than 0x80
    # outputs the quoted representation of the instruction that generates the character
    funx = fun(swaps() + push('\x00') + out() + push('\x80') + out() + push('\x80') + bxors() + out(), 2)

    # for current char c on stack
    # check if c >= 0x80, if so call funx to print the quoted representation of a char >= 0x80
    # if not, print the character directly
    redo_p = fun(dups() + push('\x80') + bands() + dups() + ccall(2) + push('\x80') + bxors() + ccall(1), 3)

    # Call redo_p in a loop, then go back to loop start p_s_q_loop
    out_s_q_loop = fun(call(3) + call(5), 4)

    # Outputs the current control character in the data rep (either \x00 or \x01)
    # then calls out_s_q_loop to finalize the quote loop
    p_s_q_loop = fun(dups() + out() + ccall(4), 5)

    # Starts the quote loop, recreates the function structure then calls p_s_q_loop to start the 
    # print loop of the data, then finalizes the function structure
    p_s_quoted = fun(push('\x21') + out() + push('\x80') + out() + call(5) + push('\x00') + out() + push('\xa0') + out(), 6)

    # Print current data on the stack in a loop
    out_s = fun(out() + call(8), 7)
    p_s = fun(ccall(7), 8)

    # Full program spec
    # define the functions above then
    # put the program on the stack
    # print it quoted
    # put it on the stack again
    # print the program unquoted
    prog = output + funx + redo_p + out_s_q_loop + p_s_q_loop + p_s_quoted + out_s + p_s + call(0) + call(6) + call(0) + call(8)

    # data function describing the program itself
    cfun = fun(reps(prog[::-1]), 0)
    print("======================= DATA =================")
    print(hexdump(cfun))
    print("======================= DATA =================")

    print("======================= PROGRAM =================")
    print(hexdump(prog))
    print("======================= PROGRAM =================")

    return cfun + prog

if __name__ == '__main__':
    prog_bin = program()
    print("==========PROGRAM===========")
    print(hexdump(prog_bin))
    print("==========PROGRAM===========")
    #p = process("./a.out")
    p = remote("3.93.128.89", 1214)
    p.readuntil("Length of your Assemblium sequence: ")
    p.send("%d\n" % len(prog_bin))
    p.readuntil("Enter your Assemblium sequence:\n")
    p.send(prog_bin)
    p.interactive()

Flag

AOTW{G0od_job_writing_y0ur_v3ry_0wN_quin3!}

More information

This is a py3 quine that uses the exact same strategy:

s = [
  '', 
  'def pq():', 
  "    print('s = [')", 
  '    for i, v in enumerate(s):', 
  "        print(' ' * 2 + repr(v), end='')", 
  '        if i != len(s) - 1:', 
  "            print(', ')", 
  '        else:', 
  "            print('')", 
  "    print(']')", 
  '', 
  'def puq():', 
  '    for i in s:', 
  '        print(i)', 
  'pq()', 
  'puq()', 
  ''
]

def pq():
    print('s = [')
    for i, v in enumerate(s):
        print(' ' * 2 + repr(v), end='')
        if i != len(s) - 1:
            print(', ')
        else:
            print('')
    print(']')

def puq():
    for i in s:
        print(i)
pq()
puq()